Navigation and localization is a crucial problem of robotics, as it is an essential aspect to collaboration between a human and a robot. In a human populated environment, such as an apartment, the challenges are even higher, because of the additional complexity.
Humanoid robots, due to their aspect and possibilities, are particularly adapted to human environments. However, they present specific constraints: walking makes their progress slower, less predictable than wheeled robots for example.
They are able to compensate some of their limits by performing actions which are more difficult for a standard robot, for example turning the head to look around, stepping over an obstacle etc.
Several approaches already exist to provide a robot with a navigation system. In the french patent application n°1353295, a method to measure and correct the drift of the robot in terms of heading angle has been proposed. This allows the robot to walk in a straight line or to perform rotations with a much higher precision than the open loop walk. The aim here is to provide an absolute localization solution, with at least qualitative or partially metric information.
The richest sensor of the robot is the monocular color camera. Performing a metric visual Simultaneous Localization And Mapping (SLAM) directly is not a good idea: the odometry is not reliable enough, and it is very difficult to accurately track keypoints because of the motion blur during the walk, the limited camera field of view and the height of the robot. This implies that a topological, qualitative representation is more adapted if we do not want to compensate these drawbacks with heavy hypotheses on the environment such as a pre-built 3D map.